/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._328;

/**
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 *
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 1->3->5->2->4->NULL
 * 示例 2:
 *
 * 输入: 2->1->3->5->6->4->7->NULL
 * 输出: 2->3->6->7->1->5->4->NULL
 * 说明:
 *
 * 应当保持奇数节点和偶数节点的相对顺序。
 * 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._328
 * @ClassName: OddEvenList
 * @Author: linyaonan
 * @Date: 2020/3/26 14:47
 */
public class OddEvenList {

    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode oddNode = head;
        ListNode startEven = new ListNode(-1);
        ListNode evenNode = startEven;
        // 只有一个节点
        if (oddNode.next == null) {
            return oddNode;
        }
        while (oddNode.next != null) {
            evenNode = evenNode.next = oddNode.next;
            if (oddNode.next.next != null) {
                oddNode = oddNode.next = oddNode.next.next;
            } else {
                oddNode.next = null;
            }
        }
        // 需要偶数尾节点进行清空
        evenNode.next = null;
        oddNode.next = startEven.next;

        return head;
    }

    public ListNode oddEvenList2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode odd = head;
        // 只有一个节点
        if (odd.next == null) {
            return odd;
        }
        // 偶数链表用于记录偶数数值，否则在奇数向后移动时，偶数就丢失了
        ListNode startEven = new ListNode(-1);
        ListNode e = startEven;
        while (odd.next != null) {
            // 1. 先记录偶数内容
            startEven = startEven.next = odd.next;
            if (odd.next.next != null) {
                // 2. 奇数向后间隔移动
                odd = odd.next = odd.next.next;
            } else {
                odd.next = null;
            }
        }
        // 这块必须清空，否则还会携带一个奇数的尾部数据
        startEven.next = null;
        odd.next = e.next;

        return head;
    }

}
